314. Binary Tree Vertical Order Traversal
Medium

Given the root of a binary tree, return the vertical order traversal of its nodes' values. (i.e., from top to bottom, column by column).

If two nodes are in the same row and column, the order should be from left to right.

 

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]

Example 2:

Input: root = [3,9,8,4,0,1,7]
Output: [[4],[9],[3,0,1],[8],[7]]

Example 3:

Input: root = [3,9,8,4,0,1,7,null,null,null,2,5]
Output: [[4],[9,5],[3,0,1],[8,2],[7]]

Example 4:

Input: root = []
Output: []

 

Constraints:

  • The number of nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100
Accepted
166,063
Submissions
348,910
Seen this question in a real interview before?
Companies
Similar Questions

Average Rating: 4.62 (34 votes)

Premium

Solution


Overview

This is yet another problem about Binary Tree traversals. As one would probably know, the common strategies to traverse a Tree data structure are Breadth-First Search (a.k.a BFS) and Depth-First Search (a.k.a. DFS).

The DFS strategy can be further distinguished as preorder DFS, inorder DFS and postorder DFS, depending on the relative order of visit among the node itself and its child nodes.

If one is not familiar with the concepts of BFS and DFS, one can find the corresponding problems on LeetCode to practice with. Also, we have an Explore card called Queue & Stack where we cover both the BFS traversal as well as the DFS traversal. Hence, in this article, we won't repeat ourselves on these concepts.

In the problem description, we are asked to return the vertical order of a binary tree, which actually implies two sub-orders, where each node would have a 2-dimensional index (denoted as <column, row>)

tree in 2D coordinates

  • column-wise order

    If we look at a binary tree horizontally, each node can be aligned to a specific column, based on its relative offset to the root node of the tree.

    Let us assume that the root node has a column index of 0, then its left child node would have a column index of -1 and its right child node would have a column index of +1, and so on.

  • row-wise order
    Now if we put the nodes into a vertical dimension, each node would be assigned to a specific row, based on its level (i.e. the vertical distance to the root node).

    Let us assume that the root node has a row index of 0, then both its child nodes would have the row index of 1.

Given the above definitions, we can now formulate the problem as a task to order the nodes based on the 2-dimensional coordinates that we defined above.

More specifically, the nodes should be ordered by column first, and further the nodes on the same column should be ordered vertically based on their row indices.


Approach 1: Breadth-First Search (BFS)

Intuition

With the formulation of the problem in the overview section, one of the most intuitive solutions to tackle the problem would be applying the BFS traversal, where the nodes would be visited level by level.

With the BFS traversal, we naturally can guarantee the vertical order of the visits, i.e. the nodes at higher levels (large row values) would get visited later than the ones at lower levels.

However, we are still missing the horizontal order ( the column order). To ensure this order, we need to do some additional processing during the BFS traversal.

The idea is that we keep a hash table (let's denote it as columnTable<key, value>), where we keep the node values grouped by the column index.

The key in the hash table would be the column index, and the corresponding value would be a list which contains the values of all the nodes that share the same column index.

In addition, the values in the corresponding list should be ordered by their row indices, which would be guaranteed by the BFS traversal as we mentioned before.

Algorithm

We elaborate on the steps to implement the above idea.

  • First, we create a hash table named columnTable to keep track of the results.

  • As to the BFS traversal, a common code pattern would be to use a queue data structure to keep track of the order we need to visit nodes. We initialize the queue by putting the root node along with its column index value (0).

  • We then run the BFS traversal with a loop consuming the elements from the queue.

  • At each iteration within the BFS, we pop out an element from the queue. The element consists of a node and its corresponding column index. If the node is not empty, we then populate the columnTable with the value of the node. Subsequently, we then put its child nodes along with their respective column indices (i.e. column-1 and column+1) into the queue.

  • At the end of the BFS traversal, we obtain a hash table that contains the desired node values grouped by their column indices. For each group of values, they are further ordered by their row indices.

  • We then sort the hash table by its keys, i.e. column index in ascending order. And finally we return the results column by column.

Complexity Analysis

  • Time Complexity: O(NlogN)\mathcal{O}(N \log N) where NN is the number of nodes in the tree.

    In the first part of the algorithm, we do the BFS traversal, whose time complexity is O(N)\mathcal{O}(N) since we traversed each node once and only once.

    In the second part, in order to return the ordered results, we then sort the obtained hash table by its keys, which could result in the O(NlogN)\mathcal{O}(N \log N) time complexity in the worst case scenario where the binary tree is extremely imbalanced (for instance, each node has only left child node.)

    As a result, the overall time complexity of the algorithm would be O(NlogN)\mathcal{O}(N \log N).

  • Space Complexity: O(N)\mathcal{O}(N) where NN is the number of nodes in the tree.

    First of all, we use a hash table to group the nodes with the same column index. The hash table consists of keys and values. In any case, the values would consume O(N)\mathcal{O}(N) memory. While the space for the keys could vary, in the worst case, each node has a unique column index, i.e. there would be as many keys as the values. Hence, the total space complexity for the hash table would still be O(N)\mathcal{O}(N).

    During the BFS traversal, we use a queue data structure to keep track of the next nodes to visit. At any given moment, the queue would hold no more two levels of nodes. For a binary tree, the maximum number of nodes at a level would be N+12\frac{N+1}{2} which is also the number of leafs in a full binary tree. As a result, in the worst case, our queue would consume at most O(N+122)=O(N)\mathcal{O}(\frac{N+1}{2} \cdot 2) = \mathcal{O}(N) space.

    Lastly, we also need some space to hold the results, which is basically a reordered hash table of size O(N)\mathcal{O}(N) as we discussed before.

    To sum up, the overall space complexity of our algorithm would be O(N)\mathcal{O}(N).




Approach 2: BFS without Sorting

Intuition

In the previous approach, it is a pity that the sorting of results overshadows the main part of the algorithm which is the BFS traversal. One might wonder if we have a way to eliminate the need for sorting. And the answer is yes.

The key insight is that we only need to know the range of the column index (i.e. [min_column, max_column]). Then we can simply iterate through this range to generate the outputs without the need for sorting.

The above insight would work under the condition that there won't be any missing column index in the given range. And the condition always holds, since there won't be any broken branch in a binary tree.

Algorithm

To implement this optimization, it suffices to make some small modifications to our previous BFS approach.

During the BFS traversal, we could obtain the range of the column indices, i.e. with the variable of min_column and max_column.

At the end of the BFS traversal, we would then walk through the column range [min_column, max_column] and retrieve the results accordingly.

Current
1 / 14

Complexity Analysis

  • Time Complexity: O(N)\mathcal{O}(N) where NN is the number of nodes in the tree.
    Following the same analysis in the previous BFS approach, the only difference is that this time we don't need the costy sorting operation (i.e. O(NlogN)\mathcal{O}(N \log N)).

  • Space Complexity: O(N)\mathcal{O}(N) where NN is the number of nodes in the tree. The analysis follows the same logic as in the previous BFS approach.


Approach 3: Depth-First Search (DFS)

Intuition

Although we applied a BFS traversal in both of the previous approaches, it is not impossible to solve the problem with a DFS traversal.

As we discussed in the overview section, once we assign a 2-dimensional index (i.e. <column, row>) for each node in the binary tree, to output the tree in vertical order is to sort the nodes based on the 2-dimensional index, firstly by column then by row, as shown in the following graph.

tree to table

Compared to the DFS traversal, the BFS traversal gives us a head start, since the nodes in higher rows would be visited later than the ones in the lower lows. As a result, we only need to focus on the column order.

That being said, we could simply traverse the tree in any DFS order (preorder, inorder or postorder), then we sort the resulting list strictly based on two keys <column, row>, which would give us the same results as the BFS traversal.

An important note is that two nodes might share the same <column, row>, in the case, as stated in the problem, the order between these two nodes should be from left to right as we did for BFS traversals. As a result, to ensure such a priority, one should make sure to visit the left child node before the right child node during the DFS traversal.

Algorithm

  • Here we implement the above algorithm, with the trick that we applied in Approach 2 (BFS without sorting) where we obtained the range of column during the traversal.

  • First, we conduct a DFS traversal on the input tree. During the traversal, we would then build a similar columnTable with the column index as the key and the list of (row, val) tuples as the value.

  • At the end of the DFS traversal, we iterate through the columnTable via the key of column index. Accordingly, we have a list of (row, val) tuples associated with each key. We then sort this list, based on the row index.

  • After the above steps, we would then obtain a list of node values ordered firstly by its column index and then by its row index, which is exactly the the vertical order traversal of binary tree as defined in the problem.

Complexity Analysis

  • Time Complexity: O(WHlogH))\mathcal{O}\big(W \cdot H \log{H})\big) where WW is the width of the binary tree (i.e. the number of columns in the result) and HH is the height of the tree.
    In the first part of the algorithm, we traverse the tree in DFS, which results in O(N)\mathcal{O}(N) time complexity.

    Once we build the columnTable, we then have to sort it column by column.

    Let us assume the time complexity of the sorting algorithm to be O(KlogK)\mathcal{O}(K \log K) where KK is the length of the input. The maximal number of nodes in a column would be H2\frac{H}{2} where HH is the height of the tree, due to the zigzag nature of the node distribution. As a result, the upper bound of time complexity to sort a column in a binary tree would be O(H2logH2)\mathcal{O}(\frac{H}{2} \log \frac{H}{2}).

    Since we need to sort WW columns, the total time complexity of the sorting operation would then be O(W(H2logH2))=O(WHlogH)\mathcal{O}\big(W \cdot (\frac{H}{2} \log{\frac{H}{2}})\big) = \mathcal{O}(W \cdot H \log{H}) . Note that, the total number of nodes NN in a tree is bounded by WHW \cdot H, i.e. N<WH N < W \cdot H . As a result, the time complexity of O(WHlogH)\mathcal{O}\big(W \cdot H \log{H}\big) will dominate the O(N)\mathcal{O}(N) of the DFS traversal in the first part.

    At the end of the DFS traversal, we have to iterate through the columnTable in order to retrieve the values, which will take another O(N)\mathcal{O}(N) time.

    To sum up, the overall time complexity of the algorithm would be O(WHlogH)\mathcal{O}\big(W \cdot H \log{H}\big).

    An interesting thing to note is that in the case where the binary tree is completely imbalanced (e.g. node has only left child.), this DFS approach would have the O(N)\mathcal{O}(N) time complexity, since the sorting takes no time on columns that contains only a single node. While the time complexity for our first BFS approach would be O(NlogN)\mathcal{O}{(N \log N)}, since we have to sort the NN keys in the columnTable.

  • Space Complexity: O(N)\mathcal{O}(N) where NN is the number of nodes in the tree.

    We kept the columnTable which contains all the node values in the binary tree. Together with the keys, it would consume O(N)\mathcal{O}(N) space as we discussed in previous approaches.

    Since we apply the recursion for our DFS traversal, it would incur additional space consumption on the function call stack. In the worst case where the tree is completely imbalanced, we would have the size of call stack up to O(N)\mathcal{O}(N).

    Finally, we have the output which contains all the values in the binary tree, thus O(N)\mathcal{O}(N) space.

    So in total, the overall space complexity of this algorithm remains O(N)\mathcal{O}(N).

Report Article Issue

Comments: 37
nd2n8's avatar
Read More

This problem should be classified as hard. Thanks for the detailed solution.

100
Show 4 replies
Reply
Share
Report
DylanLesko's avatar
Read More

How can someone (without already knowing the solution solve this problem in under a typical 15mins coding interview session?

37
Show 9 replies
Reply
Share
Report
8080dk's avatar
Read More

Related topics should be 'BFS' or 'DFS' instead of hashtable. Hashtable is actually not required.

8
Show 1 reply
Reply
Share
Report
kumom's avatar
Read More

I think it's worth mentioning in Solution 3 "columnTable[col].sort(key=lambda x:x[0])" preserves the order...It's the reason why nodes of same column and same row can be printed out from left to right

5
Reply
Share
Report
embedded2's avatar
Read More

I think there's an error in the following answer of example #3: [
[4],
[9,5],
[3,0,1],
[8,2],
[7]
]

the order of [8,2] is wrong as 8 is on the right side - it should be [2,8]

7
Show 4 replies
Reply
Share
Report
vcrishu4's avatar
Read More

The first algorithm can be improved to linear time just by tracking a min variable which stores minimum column index.
..../////

int column = 0;
int min = 0;
queue.offer(new Pair(root, column));

while (!queue.isEmpty()) {
  Pair<TreeNode, Integer> p = queue.poll();
  root = p.getKey();
  column = p.getValue();

  if (root != null) {
    if (!columnTable.containsKey(column)) {
      columnTable.put(column, new ArrayList<Integer>());
    }
    columnTable.get(column).add(root.val);
    if(min>column){
        min=column;
    }
    queue.offer(new Pair(root.left, column - 1));
    queue.offer(new Pair(root.right, column + 1));
  }
}

And then no need of sorting. just store the columnTable values starting from min, iterating columnTable.keySet().size() times.
///

int size = columnTable.keySet().size();
for(int i = 0; i < size; i++){
output.add(columnTable.get(min++));
}

6
Reply
Share
Report
liaison's avatar
Read More

hi @kumom it is a valid point to use the heap data structure in order to avoid the sorting operation at the end. But it won't completely eliminate the cost to have the final results sorted. An insertion operation in heap would take O(log n) time.

3
Show 1 reply
Reply
Share
Report
defaultProgrammer's avatar
Read More

The slides for Approach 2 are very helpful, thank you!

0
Reply
Share
Report
mohit2494's avatar
Read More

class Solution:
    def verticalOrder(self, root: TreeNode) -> List[List[int]]:
        if not root: return
        q = collections.deque([(root,0)])
        nodemap = collections.defaultdict(lambda:list())
        min_col, max_col = float('inf'), -float('inf')
        while q:
            node, col = q.popleft()
            min_col, max_col = min(min_col, col), max(max_col, col)
            nodemap[col].append(node.val)
            if node.left:
                q.append((node.left, col-1))
            if node.right:
                q.append((node.right, col+1))
        ans = []
        for c in range(min_col, max_col+1):
            ans.append(nodemap[c])
        return ans

0
Reply
Share
Report
zeem710's avatar
Read More

There is no need of finding both min and max index.
min is enough.
Sample code below:


class Solution {
    int least = Integer.MAX_VALUE;
    Map<Integer, List<Integer>> data = new HashMap();
    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> order = new ArrayList();
        if(root == null) {
            return order;
        }
        bfs(root);
        int i = 0;
        while (i < data.size()) {
            List<Integer> temp = data.get(i + least);
            order.add(temp);
            i++;
        }
        return order;
    }
    private void bfs(TreeNode root) {
        Queue<Entry<TreeNode, Integer>> queue = new LinkedList();
        queue.add(new SimpleEntry(root, 0));
        while(!queue.isEmpty()) {
            Entry<TreeNode, Integer> current = queue.poll();
            TreeNode node = current.getKey();
            int tempCol = current.getValue();
            
            if(least > tempCol) least = tempCol;
            addToMap(node, tempCol);
            
            if(node.left != null) queue.add(new SimpleEntry(node.left, tempCol - 1));
            if(node.right != null) queue.add(new SimpleEntry(node.right, tempCol + 1));
        }
    }
    private void addToMap(TreeNode node, int column) {
        List<Integer> temp = data.getOrDefault(column, new ArrayList());
        temp.add(node.val);
        data.put(column, temp);
    }
}

0
Show 1 reply
Reply
Share
Report

You don't have any submissions yet.

314/1883
Contribute
|||
Saved
#301 Remove Invalid Parentheses
Hard
#302 Smallest Rectangle Enclosing Black Pixels
Hard
#303 Range Sum Query - Immutable
Easy
#304 Range Sum Query 2D - Immutable
Medium
#305 Number of Islands II
Hard
#306 Additive Number
Medium
#307 Range Sum Query - Mutable
Medium
#308 Range Sum Query 2D - Mutable
Hard
#309 Best Time to Buy and Sell Stock with Cooldown
Medium
#310 Minimum Height Trees
Medium
#311 Sparse Matrix Multiplication
Medium
#312 Burst Balloons
Hard
#313 Super Ugly Number
Medium
#314 Binary Tree Vertical Order Traversal
Medium
#315 Count of Smaller Numbers After Self
Hard
#316 Remove Duplicate Letters
Medium
#317 Shortest Distance from All Buildings
Hard
#318 Maximum Product of Word Lengths
Medium
#319 Bulb Switcher
Medium
#320 Generalized Abbreviation
Medium
#321 Create Maximum Number
Hard
#322 Coin Change
Medium
#323 Number of Connected Components in an Undirected Graph
Medium
#324 Wiggle Sort II
Medium
#325 Maximum Size Subarray Sum Equals k
Medium
#326 Power of Three
Easy
#327 Count of Range Sum
Hard
#328 Odd Even Linked List
Medium
#329 Longest Increasing Path in a Matrix
Hard
#330 Patching Array
Hard
#331 Verify Preorder Serialization of a Binary Tree
Medium
#332 Reconstruct Itinerary
Medium
#333 Largest BST Subtree
Medium
#334 Increasing Triplet Subsequence
Medium
#335 Self Crossing
Hard
#336 Palindrome Pairs
Hard
#337 House Robber III
Medium
#338 Counting Bits
Easy
#339 Nested List Weight Sum
Medium
#340 Longest Substring with At Most K Distinct Characters
Medium
#341 Flatten Nested List Iterator
Medium
#342 Power of Four
Easy
#343 Integer Break
Medium
#344 Reverse String
Easy
#345 Reverse Vowels of a String
Easy
#346 Moving Average from Data Stream
Easy
#347 Top K Frequent Elements
Medium
#348 Design Tic-Tac-Toe
Medium
#349 Intersection of Two Arrays
Easy
#350 Intersection of Two Arrays II
Easy